#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

void QuickSort(vector<int>& a, int left, int right)
{
    if(left >= right) return;
    int begin = left, end = right, cur = left;
    int key = a[rand() % (right - left + 1) + left];
    while(cur <= right)
    {
        if(a[cur] < key) swap(a[cur++], a[left++]);
        else if(a[cur] > key) swap(a[cur], a[right--]);
        else cur++;
    }
    QuickSort(a, begin, left - 1);
    QuickSort(a, right + 1, end);
}

void MergeSort(vector<int>& a, int left, int right, vector<int>& tmp)
{
    if(left >= right) return;

    int mid = (left + right) / 2;
    MergeSort(a, left, mid, tmp);
    MergeSort(a, mid + 1, right, tmp);

    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] <= a[begin2]) tmp[index++] = a[begin1++];
        else tmp[index++] = a[begin2++];
    }
    while(begin1 <= end1) tmp[index++] = a[begin1++];
    while(begin2 <= end2) tmp[index++] = a[begin2++];
    for(int i = left; i <= right; i++) a[i] = tmp[i];
}

int main()
{
    srand(time(nullptr));
    vector<int> a = {6,0,1,7,4,8,2,9,5};

    //QuickSort(a, 0, a.size() - 1);
    vector<int> tmp(a.size(), 0);
    MergeSort(a, 0, a.size() - 1, tmp);

    for(auto& e : a) cout << e << ' ';
    cout << endl;
    return 0;
}